package com.ting.test.algorithms.大厂刷题班;

import java.util.ArrayList;
import java.util.List;

/**
 * 有一个电话号码组合
 * 返回号码能够组成的所有字符串的个数
 * 利用深度优先遍历
 */
public class 电话号码的组合问题 {


    public static char[][] phone = {
            {}, // 2    0
            {}, // 2    0
            {'a', 'b', 'c'}, // 2    0
            {'d', 'e', 'f'}, // 3    1
            {'g', 'h', 'i'}, // 4    2
            {'j', 'k', 'l'}, // 5    3
            {'m', 'n', 'o'}, // 6
            {'p', 'q', 'r', 's'}, // 7
            {'t', 'u', 'v'},   // 8
            {'w', 'x', 'y', 'z'}, // 9
    };


    public static void main(String[] args) {
        String nums = "23";
        char[] path = new char[3];
        List<String> ans = new ArrayList<>();
        int s = prpcess(nums, 0, path, ans);
    }

    /**
     * 该函数返回的是 0到index-1已经匹配完了，从index ~arr.length能够有多少种组合
     *
     * @param nums  表示输入的电话号码
     * @param index 当前匹配到的位置
     * @param path  当前组合的字符串
     * @param ans   结果集
     * @return
     */
    private static int prpcess(String nums, int index, char[] path, List<String> ans) {
        if (index == nums.length()) {
            ans.add(new String(path));
        }

        final char[] chars = nums.toCharArray();
        int i = chars[index] - 'a';
        char[] curchars = phone[i];
        for (int j = 0; j < curchars.length; j++) {
            path[index] = curchars[j];
            prpcess(nums, index + 1, path, ans);
        }

        return ans.size();
    }
}
